最小生成树及特殊生成树

前言

牢记住一句话：如果对一个算法没完全理解的话，是很难再有进步的！！

最小生成树算是最基础的图论了，反正我差不多是背板子来的

今天做完一道题，被dalao巧妙的思路震撼了，其实证明还是挺重要的

各种性质

推论\(1\)：一个图中的最小生成树可能存在多个

\(~~~~~\)证明：这个不说也能想到吧，多个点\((>2)\)的环权值相同，生成树个数为点数

推论\(2\)：对于点\(x\)，其所在的权值最小边\((x,y)\)，一定存在于某个最小生成树

\(~~~~~\)证明：假设\(x—y\)是间接连接的\(x—a—b—y\)，其联通效果等价于\(a—b—y—x\)，而不同点在

\(~~~~~~~~~~~~~\)于\(x—a\)与\(x—y\)，\((x,y)\leqslant(x,y)\)

推论\(3\)：从最小生成树外一点连一条最短边到此树，仍生成最小生成树

\(~~~~~\)证明：利用推论\(2\)易证出，反复把之前的看作一个点然后向联通块外连边，至此我们已证出\(Prim\)算法

推论\(4\)：\(Kruskal\)算法

\(~~~~~\)证明：利用推论\(5\)易证出，我们一直在重复加入点，至此我们已证出\(Kruskal\)算法

推论\(5\)：对于两个不同的最小生成树\((A,B)\)，其边权值排序后的有序集相同\((w(a1),w(a2),w(a3)......w(an))=(w(b1),w(b2),w(b3)......w(bn))\)

\(~~~~~\)证明：假设第一个不同的边\(a_i≠b_i\)

\(~~~~~~~~~~~~~\)情况\(1\)：树\(A\)包括\(b_i\)，则存在\(j>i,b_i=a_j,a_i\)~\(a_j=b_i\)，则\(a_i=a_j\)

\(~~~~~~~~~~~~~\)情况\(2\)：树\(A\)不包括\(b_i\)，则将\(b_i\)加入树\(A\)，其所在环所有边都\(≤b_i\)(因为这是最小生成树)，其中至少

\(~~~~~~~~~~~~~\)有一边不在树\(B\)内，则存在\(j≥i,b_i=a_j,a_i\)~\(a_j=b_i\)，则\(a_i=a_j\)

\(~~~~~~~~~~~~~\)证毕

推论\(6\)：无边值相同的边的图仅一个最小生成树，最小生成树里所以边值于原图无边值相同的边的图仅一个最小生成树

\(~~~~~\)证明：根据推论\(3\)，对于两个不同的最小生成树\((A,B)\)，其边权值排序后的有序集相同，既然没有边值相

\(~~~~~~~~~~~~~\)同的边自然仅一个最小生成树

推论\(7\)：不同最小生成树相同权值的边连起来后联通块状态相同

\(~~~~~\)证明：我们首先考虑权值最小的边，全部连起来后并去掉环，显然不同的方案集合都是是相同的

\(~~~~~~~~~~~~~\)那么次小权值的边呢？我们将之间得到的集合缩点，因为这个集合的点不可能再互相连边了

\(~~~~~~~~~~~~~\)次小权值边就成当前最小权值的边，同上

推论\(8\)：最小生成树两点间最大值最小

\(~~~~~\)证明：这个随便证吧

\(Kruskal\)特殊生成树

无向带权图，每次查询两点间所有路径的最大值，且最大值最小

\((u,v,d)\)找到\(u,v\)的祖先\(fu,fv\)新建节点\(node\)，该节点值为\(d\)，\(f[fu,fv]=node\)

查询时查询\(lca\)就好了

例题

归程

利用水深找到\(lca\)，里面的联通，维护子树内到点\(1\)的最小值

总结

最近陆续把这种推论性的东西写一遍吧

牢记住一句话：如果对一个算法没完全理解的话，是很难再有进步的！！